package codetop.microsoft.T10;

/**
 * @Author: 18362
 * @Create: 2022-08-15 12:34:22 星期一
 */
class Solution {
    public boolean isMatch(String s, String p) {
        char[] pattern = getPattern(p);
        boolean[] dp = new boolean[pattern.length + 1];
        dp[0] = true;
        for (int i=1; i<dp.length; ++i) {
            if (dp[i-1] && isMatch(pattern[i-1], '-', false))
                dp[i] = true;
        }
        for (int i=0; i<s.length(); ++i) {
            boolean last = dp[0];
            dp[0] = false;
            char c = s.charAt(i);
            for (int j=0; j<pattern.length; ++j) {
                boolean temp = dp[j+1];
                if (last && isMatch(pattern[j], c, false))
                    dp[j+1] = true;
                else if (dp[j] && isMatch(pattern[j], '-', false))
                    dp[j+1] = true;
                else if (dp[j+1] && isMatch(pattern[j], c, true))
                    dp[j+1] = true;
                else
                    dp[j+1] = false;
                last = temp;
            }
        }
        return dp[dp.length-1];
    }

    private boolean isMatch(char pattern, char c, boolean isMore) {
        if (pattern == '+')
            return true;
        if (c == '-')
            return pattern >= 'A' && pattern <= 'Z';
        if (pattern == '.')
            return !isMore;
        if (isMore)
            return pattern >= 'A' && pattern <= 'Z' && pattern - 'A' == c - 'a';
        return pattern == c || pattern - 'A' == c - 'a';
    }

    private char[] getPattern(String p) {
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (i < p.length()) {
            char c = p.charAt(i);
            if (c >= 'a' && c <= 'z') {
                if (i+1 < p.length() && p.charAt(i+1) == '*')
                    sb.append((char) (c - 'a' + 'A'));
                else
                    sb.append(c);
            } else if (c == '.') {
                if (i+1 < p.length() && p.charAt(i+1) == '*')
                    sb.append('+');
                else
                    sb.append('.');
            }
            ++i;
        }
        return sb.toString().toCharArray();
    }
}